

```C++
/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* next;
    Node* random;
    
    Node(int _val) {
        val = _val;
        next = NULL;
        random = NULL;
    }
};
*/
class Solution {
public:
    Node* copyRandomList(Node* head) {
        if (head == nullptr) {
            return nullptr;
        }

        // 复制每个节点，把新节点直接插到原节点的后面
        //初始化为head，cur不为空，每次跳两格
        for (auto cur = head; cur!=NULL; cur = cur->next->next){
            //第一个参数是值，第二个参数是下一个指针，再下一个是随机指针
            cur->next = new Node(cur->val, cur->next, nullptr);
        }

        // 遍历交错链表中的原链表节点
        //于上面一样，初始化为head，cur不为空，每次跳两格
        for (Node* cur = head; cur!=NULL; cur = cur->next->next) {
            if (cur->random!=NULL) {
                // 要复制的 random 是 cur->random 的下一个节点
                cur->next->random = cur->random->next;
            }
        }

        // 把交错链表分离成两个链表
        auto newhead = head->next;
        auto cur = head;
        for (; cur->next->next; cur = cur->next) {
            Node* copy = cur->next;
            cur->next = copy->next;        // 恢复原节点的 next
            copy->next = copy->next->next; // 设置新节点的 next
        }
        cur->next = nullptr; // 恢复原节点的 next
        return newhead;
    }
};

```
